/* 
 * File:   deso21.cpp
 * Author: trunghpb
 *
 * Created on March 21, 2010, 4:20 PM
ĐỀ SỐ 21
Một người quản lý có n công việc cần thực hiện cùng một lúc. Biết rằng có n công nhân, mỗi công nhân đều có thể thực hiện được tất cả các công việc nhưng với thời gian khác nhau. Thời gian để công nhân thứ i thực hiện công việc j là Ci,j (tính theo giờ). Hãy viết chương trình tìm cách sắp xếp n công việc cho n công nhân sao cho tổng thời gian thực hiện là nhỏ nhất.
Dữ liệu vào được cho bởi file: VIEC.INP trong đó:
- Dòng thứ nhất ghi số N ;
- N dòng tiếp theo ghi các giá trị của ma trận thời gian C. Hai phần tử khác nhau được viết cách nhau một vài khoảng trống.
Kết quả tìm được lưu vào file KETQUA.OUT trong đó:
- Dòng thứ nhất ghi giá trị tổng thơi gian nhỏ nhất có thể đạt được
- Dòng thứ hai ghi cách bố trí việc cho từng ông thợ.

VIEC.INP
6
10  64  57  29  18  15
34  20  19  71  16  12
57  49  40  16  11  19
29  21  46  26  21  18
28  16  11  21  21  37
15  12  15  48  37  30

KETQUA.OUT
82
1    6    5    3    4    2

 */

#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int c[MAX][MAX];
int N;
int tho[MAX], tmp[MAX];
int chuaxet[MAX];
long mint;

void input(){
    FILE *fi;
    fi = fopen("viec.inp", "r");
    fscanf(fi, "%d\n", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            fscanf(fi, "%d", &c[i][j]);
        }
        fscanf(fi, "\n");
    }
    fclose(fi);
}
void init(){
    for(int i=0; i<N; i++){
        chuaxet[i] = TRUE;
    }
    mint = 2000000000;
}

void updateMin(long total){
    mint = total;
    for(int i=0; i<N; i++){
        tho[i] = tmp[i];
    }
}

void phan_viec(int u, long total){
    if (u == N){
        if (total < mint) updateMin(total);
    }else{
        for(int i = 0; i<N; i++){
            if (chuaxet[i]){
                chuaxet[i] = FALSE;
                tmp[u] = i;
                phan_viec(u+1, total+c[u][i]);
                chuaxet[i] = TRUE;
            }
        }
    }
}

void output(){
    FILE *fo;
    fo = fopen("ketqua.out", "w");
    fprintf(fo, "%d\n", mint);
    for(int i=0; i<N; i++) {
        fprintf(fo, "%d ", tho[i]+1);
    }
    fprintf(fo, "\n");
    for(int i=0; i<N; i++) {
        fprintf(fo, "%d ",c[i][tho[i]]);
    }
    fclose(fo);
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();
    init();
    phan_viec(0, 0);
    output();
    return (EXIT_SUCCESS);
}

